package com.explorati.LeetCode68.lowestCommonAncestor;

/**
 * @ Author : Weijian_Wang
 * @ Date : Created in 11:54 2020/9/19 0019
 * @ Description ：
 */
public class Solution {
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }

    /**
     * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 将p设为值小的一方
        if(p.val > q.val) {
            TreeNode temp = new TreeNode(-1);
            temp = p;
            p = q;
            q = temp;
        }

        //如果p和q分布在root两侧，root即为返回的节点
        //如果p、q都小于root，那么遍历root的左子树寻找
        //如果p、q都大于root，那么便遍历root的右子树寻找
        if(p.val <= root.val && q.val >= root.val) {
            return root;
        } else if(p.val < root.val && q.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        }else {
            return lowestCommonAncestor(root.right, p, q);
        }
    }
}
